/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package ia1_practica3;


import java.util.List;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 *
 * @author Edson Salazar
 */
public class NodoArbol {

    Casilla casilla;
    int posx=0;
    int posy=0;
    int aposx=0;
    int aposy=0;    
    
    private int id_pos;
    private int nivel;
    private int puntuacion = 0;
    private int puntuacionAnt = 0;
    NodoArbol padre;
    private List<NodoArbol> hijos;
    /**
     * @param emcuentro esta variable tendrá la información de cada busqueda
     */
    public String encuentro = "";

    /*
     *@param Elemento es el identificador del nodo
     */
    public NodoArbol(int id_pos,Casilla casilla,int posx,int posy,int aposx,int aposy) {
        this.casilla=casilla;
        this.posx=posx;
        this.posy=posy;
        this.aposx=aposx;
        this.aposy=aposy;
        this.id_pos = id_pos;
        hijos = new ArrayList<NodoArbol>();
    }

    /**
     *@param distancia es la distancia que existe del antecesor a este
     */
    public void setpuntuacion(int dist) {
        puntuacion = dist;
    }

    /**
     * @param nivel este es el nivel en el que se encuentra en el arbol
     *
     */
    public void setnivel(int nivel) {
        this.nivel = nivel;
    }

    /*
     *@param Elemento es el identificador del nodo
     */
    public int getElemento() {
        return id_pos;
    }

    /**
     * Devuelve la distancia existente entre el nodo actual hasta el inicio.
     * Util en el algoritmo A*
     * @return 
     */
    public int getpuntuacionAnt() {
        return puntuacionAnt;
    }

    /**
     * Modifica el valor de distancia del nodo anterior (Algoritmo A*)
     * @param distanciaAnt 
     */
    public void setDistanciaAnt(int distanciaAnt) {
        this.puntuacionAnt = distanciaAnt;
    }

    /*
     *@param hijo será de tipo NodoArbol y almacenara información para que pueda ser accedida por el padre
     */
    public void addHijo(NodoArbol hijo) {
        hijos.add(hijo);
    }
    /*
     * Cada nodo podra tener una lista de hijos
     */

    public List<NodoArbol> getHijos() {
        return hijos;
    }

    public void ordenarLista(List<NodoArbol> lista) {
        //int mayor = 0;
        NodoArbol aux;
        if (lista.isEmpty()) {
            return;
        }
//        NodoArbol[] arreglo = new NodoArbol[hijos.size()];
//        for(int i=0; i<hijos.size(); i++){
//            hijos.get(i).setDistanciaAnt(this.distancia);
//            arreglo[i] = hijos.get(i);
//        }
        int pasadas = 0;
        int comparaciones = 0;
        boolean hayCambios = true;
        for (int i = 0; hayCambios; i++) {
            ++pasadas;
            hayCambios = false;
            for (int j = 0; j < lista.size() - 1; j++) {
                ++comparaciones;
                if (lista.get(j).getValAEstrella() > lista.get(j + 1).getValAEstrella()) {
                    //aux = arreglo[j];
                    aux = lista.remove(j);
                    lista.add(j+1, aux);
                    //arreglo[j] = arreglo[j+1];
                    //arreglo[j+1] = aux;
                    //intercambiar(arreglo, j, j + 1);
                    hayCambios = true;
                }
            }
        }
        //return hijos;
    }

    /**
     * indicara si el nodo tiene nodos hijo de lo contrario es un nodo hoja
     */
    public boolean esNodoHoja() {
        return hijos.size() > 0;
    }

    
    public NodoArbol Padres(int c) {
        Queue<NodoArbol> colaAuxiliar = new LinkedList<NodoArbol>();
        colaAuxiliar.add(this);
        encuentro = "";
        while (colaAuxiliar.size() != 0) {
            NodoArbol cabeza = colaAuxiliar.poll();
            encuentro += String.valueOf(cabeza.getElemento()) + "\n";
            if (cabeza.getElemento() == c) {
                return cabeza.padre;
            } else {
                for (NodoArbol hijo : cabeza.getHijos()) {
                    hijo.padre=cabeza;
                    colaAuxiliar.add(hijo);
                }
            }
        }

        return this;
    }
        
    /*
     * Una busqueda por anchura es utilizado una cola
     * @param char es el caracter que identifica el arbol
     **/
    public boolean busquedaAnchura(int c) {
        Queue<NodoArbol> colaAuxiliar = new LinkedList<NodoArbol>();
        colaAuxiliar.add(this);
        encuentro = "";
        while (colaAuxiliar.size() != 0) {
            NodoArbol cabeza = colaAuxiliar.poll();
            encuentro += String.valueOf(cabeza.getElemento())+"\n";
            if (cabeza.getElemento() == c) {
                return true;
            } else {
                for (NodoArbol hijo : cabeza.getHijos()) {
                    colaAuxiliar.add(hijo);
                }
            }
        }

        return false;
    }
    /*
     * Una busqueda por anchura es utilizado una cola
     * @param char es el caracter que identifica el arbol
     * @param nivelsearch es lo que limitara hasta que nivel se desea buscar
     **/

    public boolean busquedaAnchuraLimitada(int c, int nivelsearch) {
        Queue<NodoArbol> colaAuxiliar = new LinkedList<NodoArbol>();
        //el nodo raiz sera el nivel 0
        this.nivel = 0;
        colaAuxiliar.add(this);

        encuentro = "";
        while (colaAuxiliar.size() != 0) {
            NodoArbol cabeza = colaAuxiliar.poll();
            //System.out.println(cabeza.getElemento());  // solo añadido como informacion para nosotros
            encuentro += String.valueOf(cabeza.getElemento()) + "\n";
            if (cabeza.getElemento() == c) {
                return true;
            } else {

                if (cabeza.nivel < nivelsearch) {
                    for (NodoArbol hijo : cabeza.getHijos()) {
                        //se le asigna un nivel mayor al del nivel padre que seria uno mas que el
                        hijo.nivel = cabeza.nivel + 1;
                        colaAuxiliar.add(hijo);
                    }
                }
            }
        }

        return false;
    }

    /*
     * Una busqueda por profunidad es utilizado una pila
     * @param char es el caracter que identifica el arbol
     **/
    public boolean busquedaProfundidad(int c) {
        Stack<NodoArbol> pilaAuxiliar = new Stack<NodoArbol>();
        pilaAuxiliar.push(this);
        encuentro = "";
        while (pilaAuxiliar.size() != 0) {
            NodoArbol cabeza = pilaAuxiliar.pop();
            //System.out.println(cabeza.getElemento());  // solo añadido como informacion para nosotros
            encuentro += String.valueOf(cabeza.getElemento()) + "\n";
            if (cabeza.getElemento() == c) {
                return true;
            } else {
                for (int i = cabeza.getHijos().size() - 1; i >= 0; i--) {
                    pilaAuxiliar.push(cabeza.getHijos().get(i));
                }
            }
        }

        return false;
    }
    /*
     * Una busqueda por profunidad es utilizado una pila
     * @param char es el caracter que identifica el arbol
     * @param nivelsearch es lo que limitara hasta que nivel se desea buscar
     **/

    public boolean busquedaProfundidadLimitada(int c, int nivelsearch) {
        Stack<NodoArbol> pilaAuxiliar = new Stack<NodoArbol>();
        //el nivel raiz es 0
        this.nivel = 0;
        pilaAuxiliar.push(this);
        encuentro = "";
        while (pilaAuxiliar.size() != 0) {
            NodoArbol cabeza = pilaAuxiliar.pop();
            //System.out.println(cabeza.getElemento());  // solo añadido como informacion para nosotros
            encuentro += String.valueOf(cabeza.getElemento()) + "\n";
            if (cabeza.getElemento() == c) {
                return true;
            } else {
                if (cabeza.nivel < nivelsearch) {
                    for (int i = cabeza.getHijos().size() - 1; i >= 0; i--) {
                        //se le asigna un nivel mayor al del nivel padre que seria uno mas que el
                        cabeza.getHijos().get(i).nivel = cabeza.nivel + 1;
                        pilaAuxiliar.push(cabeza.getHijos().get(i));
                    }
                }
            }
        }

        return false;
    }
    /*
     * Se utilizo el metodo de profundidad y se modifico para que se pudiera hacer el metodo de colinas
     *
     * @param maximizar si este es true se maximiza si es false se minimiza
     */
    //

    public boolean busquedaColinas(int c, boolean maximizar) {
        Stack<NodoArbol> pilaAuxiliar = new Stack<NodoArbol>();
        this.nivel = 0;
        pilaAuxiliar.push(this);
        encuentro = "";
        while (pilaAuxiliar.size() != 0) {
            NodoArbol cabeza = pilaAuxiliar.pop();
            //System.out.println(cabeza.getElemento());  // solo añadido como informacion para nosotros
            encuentro += String.valueOf(cabeza.getElemento()) + "---" + cabeza.puntuacion + "\n";
            if (cabeza.getElemento() == c) {
                return true;
            } else {
                //como se desa maximizar o minimizar se llevara un nodo auxiliar que serviara para hacer las comparaciones
                //y guardar el mejor nodo
                NodoArbol auxnodo = null;
                if (cabeza.getHijos().size() > 0) {
                    //se obtiene el ultimo hijo y es asignado al nodo auxiliar
                    auxnodo = cabeza.getHijos().get(cabeza.getHijos().size() - 1);
                }
                for (int i = cabeza.getHijos().size() - 1; i >= 0; i--) {
                    cabeza.getHijos().get(i).nivel = cabeza.nivel + 1;
                    //se realizar comparación del nodo auxiliar con el nodo actual esto con la finalidad de maximizar
                    //o minimizar el camino
                    if (maximizar) {
                        if (auxnodo.puntuacion < cabeza.getHijos().get(i).puntuacion) {
                            auxnodo = cabeza.getHijos().get(i);
                        }
                    } else {
                        if (auxnodo.puntuacion > cabeza.getHijos().get(i).puntuacion) {
                            auxnodo = cabeza.getHijos().get(i);
                        }
                    }

                }

                if (auxnodo != null) {
                    pilaAuxiliar.push(auxnodo);
                }
            }
        }

        return false;
    }
    
    
    /*
     * Algoritmo de busqueda informada
     * @param c es el identificador del nodo que se desea buscar
     * @param maximizar si este es true se maximiza si es false se minimiza
     */
NodoArbol Auxiliar=null;
    public boolean busquedaBestFirs(int c, boolean maximizar) {
        Stack<NodoArbol> pilaAuxiliar = new Stack<NodoArbol>();
        this.nivel = 0;
        pilaAuxiliar.push(this);
        encuentro = "";
        
        while (pilaAuxiliar.size() != 0) {
            NodoArbol cabeza = pilaAuxiliar.pop();
            //System.out.println(cabeza.getElemento());  // solo añadido como informacion para nosotros
            //encuentro+=String.valueOf(cabeza.getElemento())+"---"+cabeza.distancia+"\n";

                NodoArbol auxnodo = null;
                Auxiliar=auxnodo;
                //como se desa maximizar o minimizar se llevara un nodo auxiliar que serviara para hacer las comparaciones
                //y guardar el mejor nodo
                if (cabeza.getHijos().size() > 0) {
                    //se obtiene el ultimo hijo y es asignado al nodo auxiliar
                    auxnodo = cabeza.getHijos().get(cabeza.getHijos().size() - 1);
                    Auxiliar=auxnodo;
                }
                for (int i = cabeza.getHijos().size() - 1; i >= 0; i--) {
                    cabeza.getHijos().get(i).nivel = cabeza.nivel + 1;
                    cabeza.getHijos().get(i).padre = cabeza;
                    encuentro += String.valueOf(cabeza.getElemento()) + "----" + String.valueOf(cabeza.getHijos().get(i).getElemento()) + "---" + cabeza.getHijos().get(i).puntuacion + "\n";

                    //se realizar comparación del nodo auxiliar con el nodo actual esto con la finalidad de maximizar
                    //o minimizar el camino
                    if (maximizar) {
                        if (auxnodo.puntuacion < cabeza.getHijos().get(i).puntuacion) {
                            auxnodo = cabeza.getHijos().get(i);
                            Auxiliar=auxnodo;
                        }
                    } else {
                        if (auxnodo.puntuacion > cabeza.getHijos().get(i).puntuacion) {
                            auxnodo = cabeza.getHijos().get(i);
                            Auxiliar=auxnodo;
                        }
                    }

                
                if (auxnodo != null) {
                    //se indica la mejor ruta seleccionada
                    encuentro += "Camino Seleccionado: " + cabeza.getElemento() + "----" + String.valueOf(auxnodo.getElemento()) + "---" + auxnodo.puntuacion + "\n";
                   // pilaAuxiliar.push(auxnodo);

                }
            }
        }

        return false;
    }
   

    public boolean busquedaAEstrella(char c) {
        this.nivel = 0;
        ArrayList<NodoArbol> cerrados = new ArrayList<NodoArbol>();
        //ArrayList<NodoArbol> abiertos = new ArrayList<NodoArbol>();
        java.util.HashMap<Integer, NodoArbol> abiertosAux = new java.util.HashMap<Integer, NodoArbol>();
        //abiertos.add(this);
        java.util.Iterator<NodoArbol> it;
        NodoArbol hijoTemp;
        NodoArbol actual = this;
        NodoArbol anterior = this;
        abiertosAux.put(actual.getElemento(), actual);
        while (abiertosAux.size() > 0) {
            if (actual.getElemento() == c) {
                hijoTemp = actual.padre;
                this.encuentro = "Total costo de busqueda= "+actual.getValAEstrella();
                this.encuentro = actual.getElemento()+ "; H()= "+actual.nivel + " G()= "+(actual.puntuacion+actual.puntuacionAnt)+ " F()="+ actual.getValAEstrella()+"\n"+ encuentro;
                //this.encuentro = "Ruta encontrada: \n";
                while(hijoTemp!= null){
                    encuentro = hijoTemp.getElemento()+ "; H()= "+hijoTemp.nivel + " G()= "+(hijoTemp.puntuacion+hijoTemp.puntuacionAnt)+" F()= "+ hijoTemp.getValAEstrella()+ "\n"+ encuentro;
                    hijoTemp = hijoTemp.padre;
                }
                this.encuentro = "Ruta encontrada: \n" + encuentro;
                return true;
            }
            it = actual.hijos.iterator();
            cerrados.add(actual);
            abiertosAux.remove(actual.id_pos);
            //Agregando los nuevos
            while(it.hasNext()){
                hijoTemp = it.next();
                hijoTemp.setDistanciaAnt(actual.puntuacion+actual.puntuacionAnt);
                hijoTemp.setnivel(actual.nivel+1);
                hijoTemp.padre = actual;
                if(abiertosAux.containsKey(hijoTemp.id_pos)){
                   int val = abiertosAux.get(hijoTemp.id_pos).getValAEstrella();
                   //Si es menor que el anterior se sustituye
                   if(hijoTemp.getValAEstrella() < val){
                       abiertosAux.remove(hijoTemp.id_pos);
                       abiertosAux.put(hijoTemp.id_pos, hijoTemp);
                   }
                }else{
                    abiertosAux.put(hijoTemp.id_pos, hijoTemp);
                }
            }
            if (abiertosAux.size() > 0) {
                anterior = actual;
                actual = this.getMenor(abiertosAux.values().iterator());
//                if(abiertosAux.containsKey(c)){
//                    actual = abiertosAux.get(c);
//                }else{
//                    actual = this.getMenor(abiertosAux.values().iterator());
//                }
            }
        }
        return false;
    }
    
    
    private void addListaAbiertos(NodoArbol actual, NodoArbol anterior, ArrayList<NodoArbol> lista, java.util.HashMap<Integer, NodoArbol> listaAux){
        if(listaAux.containsKey(actual.id_pos)){
            
        }else{
            lista.add(actual);
            listaAux.put(actual.id_pos, actual);
        }
    }
   
    private NodoArbol getMayor(Iterator<NodoArbol> lista){
        //int mayor = 0;
        NodoArbol aux;
        NodoArbol auxMax = null;
        if(lista.hasNext()){
            auxMax = lista.next();
            aux = auxMax;
        }
        while(lista.hasNext()){
            aux = lista.next();
            if(aux.getValAEstrella() > auxMax.getValAEstrella()){
                auxMax = aux;
            }
        }
        return auxMax;
    }
    
    private NodoArbol getMenor(Iterator<NodoArbol> lista){
        NodoArbol aux;
        NodoArbol auxMin = null;
        if(lista.hasNext()){
            auxMin = lista.next();
            aux = auxMin;
        }
        while(lista.hasNext()){
            aux = lista.next();
            if(aux.getValAEstrella() < auxMin.getValAEstrella()){
                auxMin = aux;
            }
        }
        return auxMin;
    }

    private int getValAEstrella() {
        return puntuacion + puntuacionAnt + nivel;
    }
    public int getpunteo() {
        return puntuacion;
    }

    /**
     * Insertar un nodo hijo en el nodo padre correspondiente
     * Con ayuda del algoritmo de busqueda por anchura
     * @param c
     * @param nuevoarbol
     */
    public boolean insertar_nodoArbol(int c, NodoArbol nuevoArbol) {
        Stack<NodoArbol> pilaAuxiliar = new Stack<NodoArbol>();
        pilaAuxiliar.push(this);
        encuentro = "";
        while (pilaAuxiliar.size() != 0) {
            NodoArbol cabeza = pilaAuxiliar.pop();
            //System.out.println(cabeza.getElemento());  // solo añadido como informacion para nosotros
            encuentro += String.valueOf(cabeza.getElemento()) + "\n";
            if (cabeza.getElemento() == c) {
                cabeza.addHijo(nuevoArbol);
                return true;
            } else {
                for (int i = cabeza.getHijos().size() - 1; i >= 0; i--) {
                    pilaAuxiliar.push(cabeza.getHijos().get(i));
                }
            }
        }

        return false;
    }

    /**
     * Recorren todo el arbol para realizar un .txt que servira para genera el
     * grafo por medio de la herramienta graphiv
     */
    public String generar_nodoArbol() {
        String gph_declaracion = "";
        String gph_apuntadores = "";
        Stack<NodoArbol> pilaAuxiliar = new Stack<NodoArbol>();
        pilaAuxiliar.push(this);
        encuentro = "";
        while (pilaAuxiliar.size() != 0) {
            NodoArbol cabeza = pilaAuxiliar.pop();
            //System.out.println(cabeza.getElemento());  // solo añadido como informacion para nosotros
            encuentro += String.valueOf(cabeza.getElemento()) + "\n";
            gph_declaracion += String.valueOf(cabeza.getElemento()) + ";\n";

            for (int i = cabeza.getHijos().size() - 1; i >= 0; i--) {

                System.out.println(cabeza.id_pos + "---------" + cabeza.getHijos().get(i).id_pos);
                gph_apuntadores += String.valueOf(cabeza.id_pos) + " -> " + String.valueOf(cabeza.getHijos().get(i).id_pos) + " [label=\"\"];\n";
                pilaAuxiliar.push(cabeza.getHijos().get(i));
            }
        }
        System.out.println(gph_declaracion + gph_apuntadores);
        return "digraph G\n { \n" + gph_declaracion + gph_apuntadores + "\n }";
    }

    /**
     * Recorren todo el arbol para realizar un .txt que servira para genera el
     * grafo por medio de la herramienta graphiv
     * La diferencia con el metodo anterior es que este si coloca las distancias.
     */
    public String generar_nodoArbol2() {
        String gph_declaracion = "";
        String gph_apuntadores = "";
        Stack<NodoArbol> pilaAuxiliar = new Stack<NodoArbol>();
        pilaAuxiliar.push(this);
        encuentro = "";
        while (pilaAuxiliar.size() != 0) {
            NodoArbol cabeza = pilaAuxiliar.pop();
            //System.out.println(cabeza.getElemento());  // solo añadido como informacion para nosotros
            encuentro += String.valueOf(cabeza.getElemento()) + "\n";
            gph_declaracion += String.valueOf(cabeza.getElemento()) + ";\n";

            for (int i = cabeza.getHijos().size() - 1; i >= 0; i--) {

                System.out.println(cabeza.id_pos + "---------" + cabeza.getHijos().get(i).id_pos);
                gph_apuntadores += String.valueOf(cabeza.id_pos) + " -> " + String.valueOf(cabeza.getHijos().get(i).id_pos) + " [label=\"" + String.valueOf(cabeza.getHijos().get(i).puntuacion) + "\"];\n";
                pilaAuxiliar.push(cabeza.getHijos().get(i));
            }
        }
        System.out.println(gph_declaracion + gph_apuntadores);
        return "digraph G\n { \n" + gph_declaracion + gph_apuntadores + "\n }";
    }
}
